package HighMethod03;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

class BinaryTree {
    class BtNode // binaryTreeNode
    {
        int data;
        BtNode leftchild;
        BtNode rightchild;

        public BtNode() {
            data = 0;
            leftchild = rightchild = null;
        }

        public BtNode(int x) {
            data = x;
            leftchild = rightchild = null;
        }

        public BtNode(int x, BtNode left, BtNode right) {
            data = x;
            leftchild = left;
            rightchild = right;
        }
    }

    private int nodeNum = 0;

    private BtNode root;
    private BtNode cur;

    public BinaryTree() {
        root = null;
    }

    //在begin，end范围内查找val值，返回下标
    private int FindIs(int[] in, int begin, int end, int val) {
        int pos = -1;
        for (int i = begin; i <= end; ++i) {
            if (in[i] == val) {
                pos = i;
                break;
            }
        }
        return pos;
    }

    //非递归，先序序列与中序序列创建二叉树
    private BtNode CreatePI(int[] pre, int ps, int pe, int[] in, int is, int ie) {
        BtNode s = null;
        if (pe - ps >= 0) {
            s = new BtNode(pre[ps]);
            int pos = FindIs(in, is, ie, pre[ps]);
            if (pos == -1) return null;
            int dist = pos - is;
            s.leftchild = CreatePI(pre, ps + 1, ps + dist, in, is, is + dist - 1);
            s.rightchild = CreatePI(pre, ps + dist + 1, pe, in, is + dist + 1, ie);
        }
        return s;
    }

    //非递归，中序后续创建二叉树
    private BtNode CreateIP(int[] in, int is, int ie, int[] pa, int ps, int pe) {
        BtNode s = null;
        if (ie - is >= 0) {
            s = new BtNode(pa[pe]);
            int pos = FindIs(in, is, ie, pa[pe]);
            if (pos == -1) return null;
            int dist = pos - is;
            s.leftchild = CreateIP(in, is, is + dist - 1, pa, ps, ps + dist - 1);
            s.rightchild = CreateIP(in, is + dist + 1, ie, pa, ps + dist, pe - 1);
        }
        return s;
    }

    //递归，先序遍历
    private void PreOrder(BtNode ptr) {
        if (ptr != null) {
            System.out.print(ptr.data + " ");
            PreOrder(ptr.leftchild);
            PreOrder(ptr.rightchild);
        }
    }

    //递归，中序遍历
    private void InOrder(BtNode ptr) {
        if (ptr != null) {
            InOrder(ptr.leftchild);
            System.out.print(ptr.data + " ");
            InOrder(ptr.rightchild);
        }
    }

    //递归，后序遍历
    private void PastOrder(BtNode ptr) {
        if (ptr != null) {
            PastOrder(ptr.leftchild);
            PastOrder(ptr.rightchild);
            System.out.print(ptr.data + " ");
        }
    }

    public void PreOrder() {
        PreOrder(root);
        System.out.println();
    }

    public void InOrder() {
        InOrder(root);
        System.out.println();
    }

    public void PastOrder() {
        PastOrder(root);
        System.out.println();
    }


    public void CreateTreePI(int[] pre, int[] in) {
        if (pre == null || in == null ||
                pre.length < 1 || in.length < 1
                || pre.length != in.length) {
            return;
        }
        int n = pre.length;
        root = CreatePI(pre, 0, n - 1, in, 0, n - 1);
    }

    public void CreateTreeIP(int[] in, int[] pa) {
        if (pa == null || in == null ||
                pa.length < 1 || in.length < 1
                || pa.length != in.length) {
            return;
        }
        int n = pa.length;
        root = CreateIP(in, 0, n - 1, pa, 0, n - 1);
    }


    //非递归，先序遍历
    public void NicePreOrder() {
        if (root == null) return;
        Stack<BtNode> st = new Stack<>();
        st.push(root);
        while (!st.empty()) {
            BtNode ptr = st.peek();
            st.pop();
            System.out.print(ptr.data + " ");
            if (ptr.rightchild != null) {
                st.push(ptr.rightchild);
            }
            if (ptr.leftchild != null) {
                st.push(ptr.leftchild);
            }
        }
        System.out.println();
    }

    //非递归，中序遍历
    public void NiceInOrder() {
        if (root == null) return;
        BtNode ptr = root;
        Stack<BtNode> st = new Stack<>();
        while (ptr != null || !st.empty()) {
            while (ptr != null) {
                st.push(ptr);
                ptr = ptr.leftchild;
            }
            ptr = st.peek();
            st.pop();
            System.out.print(ptr.data + " ");
            ptr = ptr.rightchild;
        }
        System.out.println();
    }

    //非递归，后序遍历
    public void NicePastOrder() {
        if (root == null) return;
        BtNode ptr = root;
        Stack<BtNode> st = new Stack<>();
        BtNode tag = null;
        while (ptr != null || !st.empty()) {
            while (ptr != null) {
                st.push(ptr);
                ptr = ptr.leftchild;
            }
            ptr = st.peek();
            st.pop();
            if (ptr.rightchild == null || ptr.rightchild == tag) {
                System.out.print(ptr.data + " ");
                tag = ptr;
                ptr = tag;
                ptr = null;
            } else {
                st.push(ptr);
                ptr = ptr.rightchild;
            }
        }
        System.out.println();
    }

    //非递归，层次遍历
    public void NiceLevelOrder() {
        if (root == null) return;
        System.out.print("层次遍历：");
        Queue<BtNode> qu = new LinkedList<>();
        qu.offer(root);
        while (!qu.isEmpty()) {
            BtNode ptr = qu.poll();
            System.out.print(ptr.data + " ");
            nodeNum++;

            if (ptr.leftchild != null) {
                qu.offer(ptr.leftchild);
            }
            if (ptr.rightchild != null) {
                qu.offer(ptr.rightchild);
            }
        }
        System.out.println();
    }

    //非递归，Z形遍历
    public void NiceOrderZ() {
        if (root == null) return;

        Stack<BtNode> atNodes = new Stack<>();
        Stack<BtNode> btNodes = new Stack<>();

        atNodes.push(root);
        BtNode node = atNodes.peek();

        while (!atNodes.isEmpty() || !btNodes.isEmpty()) {
            while (!atNodes.isEmpty()) {
                node = atNodes.peek();
                atNodes.pop();
                System.out.print(node.data + " ");

                if (node.leftchild != null) {
                    btNodes.push(node.leftchild);
                }
                if (node.rightchild != null) {
                    btNodes.push(node.rightchild);
                }
            }
            while (!btNodes.isEmpty()) {
                node = btNodes.peek();
                btNodes.pop();
                System.out.print(node.data + " ");
                if (node.rightchild != null) {
                    atNodes.push(node.rightchild);
                }
                if (node.leftchild != null) {
                    atNodes.push(node.leftchild);
                }
            }
        }
    }

    //递归的计算二叉树的深度
    public int depthOfBtree() {
        return calDepth(root);
    }

    private int calDepth(BtNode node) {
        if (node == null) return 0;
            //根节点不为空，已经有深度1
        else return Math.max(calDepth(node.leftchild), calDepth(node.rightchild)) + 1;
    }

    //非递归计算二叉树的深度
    public int getDepth() {
        if (root == null) return 0;
        int h = 0;
        Queue<BtNode> qu = new LinkedList<>();
        qu.offer(root);
        BtNode ptr;
        while (!qu.isEmpty()) {
            int n = qu.size();
            int i = 0;
            //出完一层，深度加一，（i<n）判断该层是否出完
            while (i < n) {
                ptr = qu.poll();
                if (ptr.leftchild != null) qu.offer(ptr.leftchild);
                if (ptr.rightchild != null) qu.offer(ptr.rightchild);
                ++i;
            }
            h += 1;
        }
        return h;
    }

    //计算二叉树的节点个数
    public int getNodeNumB() {
        if (root == null) return -1;

        return calNodeNum(root);
    }

    private int calNodeNum(BtNode node) {
        if (node == null) return 0;

        else return calNodeNum(node.rightchild) + calNodeNum(node.leftchild) + 1;

    }

    //判断满二叉树、方法一
    public boolean isFullBtree() {
        if (root == null) return false;

        int depth = calDepth(root);
        int sum = (int) Math.pow(2, depth) - 1;
//        层次遍历得到节点总数
        NiceLevelOrder();
        return sum == nodeNum;
    }

    //判断满二叉树，方法二
    public boolean isFullBtre() {

        int num = 1;
        boolean result = true;
        if (root == null) return result;

        Queue<BtNode> qu = new LinkedList<>();
        qu.offer(root);
        BtNode ptr;
        while (!qu.isEmpty()) {
            int n = num;
            int i = 0;
            //这里是关键的判断，判断当前层次能否出够n个数
            if (n > qu.size()) return false;
            num += num;
            //这里只是更新队列，模拟遍历
            while (i < n && !qu.isEmpty()) {
                ptr = qu.poll();
                if (ptr.leftchild != null) qu.offer(ptr.leftchild);
                if (ptr.rightchild != null) qu.offer(ptr.rightchild);
                ++i;
            }
            result = true;
        }
        return result;
    }

    //判断完全二叉树的方法一,不推荐
    public boolean isSquareBtree() {
        if (root == null) return false;

        return iSB(root);
    }

    /**
     * 判断二叉树是否是完全二叉树
     *
     * @param node
     * @return
     */
    private boolean iSB(BtNode node) {

        boolean label = false;
        Queue<BtNode> queue = new LinkedList<>();
        queue.offer(node);
        while (!queue.isEmpty()) {
            node = queue.poll();
//***********************************
            if ((node.rightchild != null && node.leftchild == null) //右孩子不等于空，左孩子等于空  -> false
                    ||
                    (label && (node.rightchild != null || node.leftchild != null)) //开启叶节点判断标志位时，如果层次遍历中的后继结点不是叶节点 -> false
            ) {
                return false;
            }
            if (node.leftchild != null) {
                queue.offer(node.leftchild);
            }
            if (node.rightchild != null) {
                queue.offer(node.rightchild);
            } else {
                label = true;
            }
        }
        return true;
    }

    //判断完全二叉树的方法二，推荐
    public boolean is_Square() {
        boolean res = true;

        if (root == null) return res;
        Queue<BtNode> qu = new LinkedList<>();
        qu.offer(root);

        while (!qu.isEmpty()) {
            BtNode ptr = qu.poll();
            if (ptr == null) break;
            qu.offer(ptr.leftchild);
            qu.offer(ptr.rightchild);
        }
        while (!qu.isEmpty()) {
            if (qu.poll() != null) {
                res = false;
                break;
            }
        }
        return res;
    }

    //查找数值的方法一
    public boolean FindValue(int val) {
        if (root == null) {
            return false;
        }
        return findValue(root, val);
    }

    private boolean findValue(BtNode ptr, int val) {
        if (ptr.data == val) return true;
        boolean left = false;
        boolean right = false;
        if (ptr.leftchild != null)
            left = findValue(ptr.leftchild, val);
        if (ptr.rightchild != null)
            right = findValue(ptr.rightchild, val);
        return left || right;
    }

    //查找数值的方法二
    public boolean FindValue2(int val) {
        boolean res = true;
        cur = findValue2(root,val);
        if(cur == null)
        {
            res = false;
        }
        return res;
    }

    private BtNode findValue2(BtNode ptr, int val) {
        if (ptr == null || ptr.data == val) return ptr;
        else {
            BtNode p = findValue2(ptr.leftchild, val);
            if (p == null) {
                p = findValue2(ptr.rightchild, val);
            }
            return p;
        }
    }




    //查找两个孩子最近的公共祖先*************
    private BtNode FindNparent(BtNode ptr,BtNode first,BtNode second) {
        //用队列、把父节点存下来、比较第一个相同的节点，即为最近公共祖先节点

        return null;
    }

    private BtNode Parent(BtNode ptr, BtNode child) {

        if (ptr == null || ptr.rightchild == child || ptr.leftchild == child) {
            return ptr;
        } else {
            BtNode p = Parent(ptr.leftchild, child);
            if (p == null) {
                p = Parent(ptr.rightchild, child);
            }
            return p;
        }
    }

    private boolean FindParent(BtNode ptr, BtNode child) {
        boolean res = false;
        cur = null;
        if (ptr != null && child != null && ptr != child) {
            cur = Parent(ptr, child);
            if (cur != null) {
                res = true;
            }
        }
        return res;
    }

    //查找当前节点curd 的父结点
    public boolean FindParent() {
        return FindParent(root, cur);
    }


}


public class Main {

    public static void main(String[] args) {
        BinaryTree myt = new BinaryTree();
        int[] pre = {3, 9, 8, 5, 10, 20, 15, 7};
        int[] in = {8, 9, 10, 5, 20, 3, 15, 7};
        int[] pa = {8, 10, 20, 5, 9, 7, 15, 3};

        //是满二叉树
        int[] preTest = {3, 9, 8, 5, 15, 10, 7};
        int[] inTest = {8, 9, 5, 3, 10, 15, 7};

        //不是满二叉树
        int[] preTest2 = {3, 9, 8, 10, 5, 15, 20};
        int[] inTest2 = {10, 8, 9, 5, 3, 20, 15};
//        myt.CreateTreePI(preTest2, inTest2);
        myt.CreateTreePI(preTest, inTest);
//        myt.CreateTreePI(pre, in);
//        myt.CreateTreeIP(in, pa);

//        myt.PreOrder();          //先序遍历
//        myt.InOrder();          //中序遍历
//        myt.PastOrder();          //后序遍历

        System.out.println("=========================");
//        myt.NicePreOrder();       //
//        myt.NiceInOrder();
//        myt.NicePastOrder();
//        myt.NiceLevelOrder();       //层次遍历

        //Z形遍历二叉树
//        myt.NiceOrderZ();

        //二叉树的深度
        System.out.println("二叉树的深度为：" + myt.depthOfBtree());
        System.out.println("二叉树的深度为：" + myt.getDepth());

        //判断是否为满二叉树
//        myt.PreOrder();
        System.out.println("是否是满二叉树：" + myt.isFullBtree());
        System.out.println("是否是满二叉树：" + myt.isFullBtre());

        //判断是否为完全二叉树
        System.out.println("是否是完全二叉树：" + myt.isSquareBtree());
        System.out.println("是否是完全二叉树：" + myt.is_Square());

        //
        System.out.println("二叉树的节点个数：" + myt.getNodeNumB());

        System.out.println("查找数值3：" + myt.FindValue(3));
        System.out.println("查找数值3的地址：" + myt.FindValue2(3));
        System.out.println("查找数值21：" + myt.FindValue(21));
        System.out.println("查找数值21的地址：" + myt.FindValue2(21));
    }

}